⟸ pàgina anterior ⟸

Exercici 12 (Tasca 1).

(pigeonhole principle)

Passejades arbitràriament llargues en grafs

Donat un graf dirigit G (amb bucles) de n vèrtexs i dos vèrtexs seus s, t, demostreu que si existeix una passejada a G de s a t de mida > n, llavors hi ha passejades arbitràriament llargues de s a t. En altres paraules, que existeix un n_0\in \mathbb N tal que per tot m\geq n_0 hi ha una passejada a G de s a t de mida \geq m.

Recordeu que una passejada de s a t en un graf G és una seqüència de vèrtexs v_0,\dots,v_\ell tal que v_0=s, v_\ell=t i, per tot i, (v_i,v_{i+1}) és una aresta a G. No es requereix que els vèrtexs o les arestes siguin diferents. La mida de la passejada és \ell.